import random

def IC_spread(G, seed_set, activation_prob=0.01, num_simulations=1000):
    """
    使用普通IC模型对种子集合在图G上进行Monte Carlo模拟
    :param G: networkx 图
    :param seed_set: 初始种子节点集合
    :param activation_prob: 边的激活概率（固定值）
    :param num_simulations: 模拟次数
    :return: 平均影响力传播节点数
    """
    total_spread = 0

    for _ in range(num_simulations):
        activated = set(seed_set)
        newly_activated = set(seed_set)

        while newly_activated:
            next_activated = set()
            for u in newly_activated:
                for v in G.neighbors(u):
                    if v not in activated:
                        if random.random() < activation_prob:
                            next_activated.add(v)
            newly_activated = next_activated
            activated.update(newly_activated)

        total_spread += len(activated)

    return total_spread / num_simulations
def WIC_spread(G, seed_set, num_simulations=1000):
    """
    在图G上使用WIC模型对种子集合进行Monte Carlo模拟
    :param G: networkx图
    :param seed_set: 初始激活节点集合（list或set）
    :param num_simulations: 模拟次数
    :return: 平均影响力（激活节点数）
    """
    total_spread = 0

    for _ in range(num_simulations):
        activated = set(seed_set)
        newly_activated = set(seed_set)

        while newly_activated:
            next_activated = set()
            for u in newly_activated:
                for v in G.neighbors(u):
                    if v not in activated:
                        prob = 1 / G.degree[v]
                        if random.random() < prob:
                            next_activated.add(v)
            newly_activated = next_activated
            activated.update(newly_activated)

        total_spread += len(activated)

    return total_spread / num_simulations
